﻿/**

 * Copyright (c) 2015-2016, FastDev 刘强 (fastdev@163.com) & Quincy.

 *

 * Licensed under the Apache License, Version 2.0 (the "License");

 * you may not use this file except in compliance with the License.

 * You may obtain a copy of the License at

 *

 *      http://www.apache.org/licenses/LICENSE-2.0

 *

 * Unless required by applicable law or agreed to in writing, software

 * distributed under the License is distributed on an "AS IS" BASIS,

 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.

 * See the License for the specific language governing permissions and

 * limitations under the License.

 */

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using OF.Notify.DataHost.Cluster;
using OF.Notify.DataHost.Cluster.Disk;

namespace OF.Notify.DataHost
{
    public class WrapedIdTreeNode
    {
        public IdTreeNode Node;
        public WrapedIdTreeNode Next;
    }

    public class MergeSession
    {
        internal bool isChanged = false;
        public int[] calArray = null;
        public string basePath = null;
        public MergeSession(string basePath, int[] calArray)
        {
            this.basePath = basePath;
            this.calArray = calArray;
        }

        public void SetUnChanged()
        {
            this.isChanged = false;
        }

        public void SetChanged()
        {
            this.isChanged = true;
        }

        public bool IsChanged()
        {
            return this.isChanged;
        }
    }

    public class MergeContext
    {
        internal bool isChanged = false;
        internal MergeSession mergeSession = null;

        public MergeContext(MergeSession mergeSession)
        {
            this.mergeSession = mergeSession;
        }

        public void SetChanged()
        {
            this.isChanged = true;
            this.mergeSession.SetChanged();
        }

        public bool IsChanged()
        {
            return isChanged;
        }
    }


    public class IdTreeNode
    {
        public int BeginIndex;
        public int EndIndex;
        public byte Level;

        public bool IsFull;

        internal IdTreeNode Next;
        internal IdTreeNode ChildRoot;

        internal WrapedIdTreeNode AddedRoot;
        internal bool IsFullChanged;

        public IdTreeNode()
        { }

        public static int[] GetCalArray(int[] countArray)
        {
            int[] calArray = new int[countArray.Length];
            calArray[0] = countArray[0];
            for (int i1 = 1; i1 < countArray.Length; i1++)
            {
                calArray[i1] = calArray[i1 - 1] * countArray[i1];
            }
            calArray = calArray.Reverse().ToArray();
            return calArray;
        }

        public static IdTreeNode NewRootNode(int maxValue)
        {
            IdTreeNode lastTreeNode = new IdTreeNode
            {
                BeginIndex = 0,
                EndIndex = maxValue,
                ChildRoot = null,
                IsFull = false,
                Next = null,
                Level = 0
            };
            return lastTreeNode;
        }

        internal static IdTreeNode GetNodeTree(int level, int[] calArray, int fileBeginIndex, int maxValue)
        {
            int minLevel = Math.Min(level, calArray.Length);
            int oldId = fileBeginIndex;
            IdTreeNode lastTreeNode = NewRootNode(maxValue);
            IdTreeNode firstNode = lastTreeNode;
            int totalOffset = 0;
            for (int i1 = 0; i1 < minLevel; i1++)
            {
                int currentPathIndex = fileBeginIndex / calArray[i1];
                int offsetI = currentPathIndex * calArray[i1];
                IdTreeNode treeNode = new IdTreeNode
                {
                    BeginIndex = totalOffset + offsetI,
                    EndIndex = totalOffset + offsetI + calArray[i1] - 1,
                    IsFull = false,
                    Next = null,
                    ChildRoot = null,
                    Level = (byte)(lastTreeNode.Level + 1)
                };
                lastTreeNode.ChildRoot = treeNode;
                lastTreeNode = treeNode;
                fileBeginIndex = fileBeginIndex - offsetI;
                totalOffset += offsetI;
            }
            lastTreeNode.IsFull = true;
            return firstNode;
        }

        public bool IsExists(int id)
        {
            lock (this)
            {
                if (this.BeginIndex > id)
                {
                    return false;
                }

                if (this.EndIndex < id)
                {
                    return false;
                }

                if (this.IsFull)
                {
                    return true;
                }
                else
                {
                    Queue<IdTreeNode> queue = new Queue<IdTreeNode>();
                    queue.Enqueue(this);
                    while (queue.Count > 0)
                    {
                        IdTreeNode node = queue.Dequeue();
                        if (node.IsFull)
                        {
                            return true;
                        }
                        else
                        {
                            Each(node.ChildRoot, (childNode) =>
                            {
                                if (childNode.BeginIndex > id)
                                {
                                    return true;
                                }

                                if (childNode.EndIndex < id)
                                {
                                    return false;
                                }

                                queue.Enqueue(childNode);
                                return false;
                            });
                        }
                    }
                }
                return false;
            }
        }

        /// <summary>
        /// Id is index from 0
        /// </summary>
        /// <param name="calArray"></param>
        /// <param name="id"></param>
        /// <returns></returns>
        public static IdTreeNode NewIdTree(int[] calArray, int id, int maxValue)
        {
            int oldId = id;
            IdTreeNode lastTreeNode = NewRootNode(maxValue);
            IdTreeNode firstNode = lastTreeNode;
            int totalOffset = 0;
            for (int i1 = 0; i1 < calArray.Length; i1++)
            {
                int currentPathIndex = id / calArray[i1];
                int offsetI = currentPathIndex * calArray[i1];
                IdTreeNode treeNode = new IdTreeNode
                {
                    BeginIndex = totalOffset + offsetI,
                    EndIndex = totalOffset + offsetI + calArray[i1] - 1,
                    IsFull = false,
                    Next = null,
                    ChildRoot = null,
                    Level = (byte)(lastTreeNode.Level + 1)
                };
                lastTreeNode.ChildRoot = treeNode;
                lastTreeNode = treeNode;
                id = id - offsetI;
                totalOffset += offsetI;
            }
            IdTreeNode endNode = new IdTreeNode
            {
                BeginIndex = oldId,
                EndIndex = oldId,
                IsFull = true,
                Next = null,
                ChildRoot = null,
                Level = (byte)(lastTreeNode.Level + 1)
            };
            lastTreeNode.ChildRoot = endNode;
            return firstNode;
        }

        public void VisitTree(Action<IdTreeNode> action)
        {
            lock (this)
            {
                Queue<IdTreeNode> queue = new Queue<IdTreeNode>();
                queue.Enqueue(this);
                while (queue.Count > 0)
                {
                    var item = queue.Dequeue();
                    action(item);

                    Each(item.ChildRoot, (childNode) =>
                    {
                        queue.Enqueue(childNode);
                        return false;
                    });
                }
            }
        }

        internal class RestoreParam
        {
            public bool IsDir;
            public string Path;
            public byte Level;
        }
        public static IdTreeNode Restore(MergeSession currentMS, int maxValue)
        {
            MergeSession ms = new MergeSession(currentMS.basePath, currentMS.calArray);
            MergeContext mc = new MergeContext(ms);
            string basePath = ms.basePath;
            IdTreeNode rootNode = NewRootNode(maxValue);
            Queue<RestoreParam> pathQueue = new Queue<RestoreParam>();
            if (Directory.Exists(basePath))
            {
                pathQueue.Enqueue(new RestoreParam { IsDir = true, Path = basePath, Level = 0 });
            }
            while (pathQueue.Count > 0)
            {
                RestoreParam pathParam = pathQueue.Dequeue();
                if (pathParam.Path.EndsWith("_"))
                {
                    int lastSep = pathParam.Path.LastIndexOf("\\");
                    string itemName = pathParam.Path.Substring(lastSep + 1);
                    int beginIndex = int.Parse(itemName.TrimEnd('_'));
                    IdTreeNode treeNode = GetNodeTree(pathParam.Level, ms.calArray, beginIndex, maxValue);
                    rootNode.MergeNode(treeNode, mc);
                    continue;
                }
                
                if (pathParam.IsDir)
                {
                    var childDir = Directory.EnumerateDirectories(pathParam.Path);
                    foreach (var dir in childDir)
                    {
                        pathQueue.Enqueue(new RestoreParam { IsDir = true, Path = dir, Level = (byte)(pathParam.Level + 1) });
                    }
                    var childFiles = Directory.EnumerateFiles(pathParam.Path);
                    foreach (var file in childFiles)
                    {
                        pathQueue.Enqueue(new RestoreParam { IsDir = false, Path = file, Level = (byte)(pathParam.Level + 1) });
                    }
                }
                else
                {
                    byte[] btArray = null;
                    ClusterContext.StringLock.Invoke(pathParam.Path, () => {
                        using (FileStream fs = new FileStream(pathParam.Path, FileMode.Open))
                        {
                            btArray = new byte[fs.Length];
                            fs.Read(btArray, 0, btArray.Length);
                        }
                    });
                    int startI = 0;
                    while (startI < btArray.Length)
                    {
                        IdTreeNode newNode = IdTreeNode.NewIdTree(ms.calArray, BitConverter.ToInt32(btArray, startI), maxValue);
                        rootNode.MergeNode(newNode, mc);
                        startI += 4;
                    }
                }
            }

            ms.SetUnChanged();
            return rootNode;
        }




       

        internal void MarkNodeUnChanged(IdTreeNode node)
        {
            node.IsFullChanged = false;
            node.AddedRoot = null;
        }

        public interface IVisitChangedNodes
        {
            void RenameFullChangedItem(MergeSession ms, IdTreeNode item);
            void SaveAddedFileItem(MergeSession ms, IdTreeNode changedParenNode);
            void CreateDirItem(MergeSession ms, IdTreeNode currentNode);
            void SaveFileAllItems(MergeSession ms, IdTreeNode changedParenNode);
        }

        public void VisitChangedNodes(MergeSession ms, IVisitChangedNodes iVisitChangedNodes)
        {
            if (!ms.IsChanged())
            {
                return;
            }

            int dirMaxLevel = ms.calArray.Length - 1;
            lock (this)
            {
                VisitTree((item) =>
                {
                    if (item.IsFullChanged)
                    {
                        iVisitChangedNodes.RenameFullChangedItem(ms, item);
                        MarkNodeUnChanged(item);
                    }
                    else if (item.AddedRoot != null)
                    {
                        SaveAddedNodes(ms, item, iVisitChangedNodes);
                        MarkNodeUnChanged(item);
                    }
                });
                ms.SetUnChanged();
            }
        }

        public class SaveChangedNodesVisitor : IVisitChangedNodes
        {
            internal void SaveLeafNode(FileStream fs, IdTreeNode node)
            {
                byte[] bytes = BitConverter.GetBytes(node.BeginIndex);
                fs.Write(bytes, 0, bytes.Length);
            }


            internal int[] GetIdPath(IdTreeNode treeNode, int[] calArray)
            {
                return GetIdPath(calArray, treeNode.BeginIndex, treeNode.Level);
            }

            internal static int[] GetIdPath(int[] calArray, int id, int level)
            {
                int minLevel = Math.Min(level, calArray.Length);
                int[] pathArray = new int[minLevel];
                int totalOffset = 0;
                for (int i1 = 0; i1 < minLevel; i1++)
                {
                    int currentPathIndex = id / calArray[i1];
                    int offsetI = currentPathIndex * calArray[i1];
                    pathArray[i1] = totalOffset + offsetI;
                    id = id - offsetI;
                    totalOffset += offsetI;
                }
                return pathArray;
            }

            internal void RenameDirectory(string oldName, string newName)
            {
                if (!Directory.Exists(newName))
                {
                    try
                    {
                        Directory.CreateDirectory(newName);
                    }
                    catch (Exception ex)
                    { 
                        
                    }
                }

                if (Directory.Exists(oldName))
                {
                    try
                    {
                        Directory.Delete(oldName, true);
                    }
                    catch (Exception ex)
                    { 
                        
                    }
                }
            }

            internal void RenameFile(string oldName, string newName)
            {
                if (!File.Exists(newName))
                {
                    DiskVisitor.EnsureFileDirectoryExists(newName);
                    using (var fs = File.Create(newName))
                    { }
                }

                DiskVisitor.SafeDeleteFile(oldName);
            }

            void IVisitChangedNodes.RenameFullChangedItem(MergeSession ms, IdTreeNode item)
            {
                int dirMaxLevel = ms.calArray.Length - 1;
                string basePath = ms.basePath;
                int[] calArray = ms.calArray;
                int[] pathIndexArr = GetIdPath(item, calArray);
                string oldName = Path.Combine(basePath, string.Join("\\", pathIndexArr));
                string newName = oldName + "_";
                if (item.Level <= dirMaxLevel)
                {
                    RenameDirectory(oldName, newName);
                }
                else
                {
                    RenameFile(oldName, newName);
                }
            }

            void IVisitChangedNodes.SaveAddedFileItem(MergeSession ms, IdTreeNode changedParenNode)
            {
                string basePath = ms.basePath;
                int[] calArray = ms.calArray;
                int[] pathIndexArr = GetIdPath(changedParenNode, calArray);
                string path = Path.Combine(basePath, string.Join("\\", pathIndexArr));
                DiskVisitor.EnsureFileDirectoryExists(path);
                ClusterContext.StringLock.Invoke(path, () => {
                    using (FileStream fs = new FileStream(path, FileMode.Append))
                    {
                        Each(changedParenNode.AddedRoot, (node) =>
                        {
                            SaveLeafNode(fs, node);
                            return false;
                        });
                        fs.Flush();
                    }
                });
            }

            void IVisitChangedNodes.CreateDirItem(MergeSession ms, IdTreeNode currentNode)
            {
                string basePath = ms.basePath;
                int[] pathIndexArr = GetIdPath(currentNode, ms.calArray);
                string oldPath = Path.Combine(basePath, string.Join("\\", pathIndexArr));
                if (!Directory.Exists(oldPath))
                {
                    try
                    {
                        Directory.CreateDirectory(oldPath);
                    }
                    catch (Exception ex)
                    { }
                }
            }

            void IVisitChangedNodes.SaveFileAllItems(MergeSession ms, IdTreeNode changedParenNode)
            {
                string basePath = ms.basePath;
                int[] calArray = ms.calArray;
                int[] pathIndexArr = GetIdPath(changedParenNode, calArray);
                string path = Path.Combine(basePath, string.Join("\\", pathIndexArr));
                DiskVisitor.EnsureFileDirectoryExists(path);
                ClusterContext.StringLock.Invoke(path, () => {
                    using (FileStream fs = new FileStream(path, FileMode.Append))
                    {
                        Each(changedParenNode.ChildRoot, (node) =>
                        {
                            SaveLeafNode(fs, node);
                            return false;
                        });
                        fs.Flush();
                    }
                });
            }
        }
     
        public void SaveChangedNodes(MergeSession ms)
        {
            IVisitChangedNodes iVisitChangedNodes = new SaveChangedNodesVisitor();
            VisitChangedNodes(ms, iVisitChangedNodes);
        }

        internal bool AppendNotInRangeIds(GetQueryNodesParam param)
        {
            if (this.IsFull)
            {
                return false;
            }
            int startI = Math.Max(this.BeginIndex, param.minValue);
            int endI = Math.Min(this.EndIndex, param.maxValue);

            Each(this.ChildRoot, (node) =>
            {
                if (param.result.Count >= param.count)
                {
                    return true;
                }

                if (node.BeginIndex > endI)
                {
                    return true;
                }

                if (startI < node.BeginIndex)
                {
                    for (; startI < node.BeginIndex; startI++)
                    {                        
                        param.result.Add(startI);
                        if (param.result.Count >= param.count)
                        {
                            return true;
                        }
                    }
                    startI = node.EndIndex + 1;
                }
                else
                {
                    if (node.EndIndex >= startI)
                    {
                        startI = node.EndIndex + 1;
                    }
                    else
                    {
                        return false;
                    }
                }
                return false;
            });

            if (param.result.Count >= param.count)
            {
                return true;
            }

            for (; startI <= endI; startI++)
            {
                param.result.Add(startI);
                if (param.result.Count >= param.count)
                {
                    return true;
                }
            }
            return false;
        }

        public class GetQueryNodesParam
        {
            public List<int> result;
            public int dirMaxLevel;
            public int minValue;
            public int maxValue;
            public int count;
        }

        public bool GetNotExistsNodes(GetQueryNodesParam param)
        {
            int fileLevel = param.dirMaxLevel + 1;
            IdTreeNode node = this;

            if (param.result.Count >= param.count)
            {
                return true;
            }

            if (this.IsFull)
            {
                return false;
            }

            if (this.BeginIndex > param.maxValue)
            {
                return false;
            }

            if (this.EndIndex < param.minValue)
            {
                return false;
            }

            lock (this)
            {
                if (node.Level < fileLevel)
                {
                    Each(node.ChildRoot, (childNode) =>
                    {
                        if (param.result.Count >= param.count)
                        {
                            return true;
                        }

                        if (childNode.BeginIndex > param.maxValue)
                        {
                            return true;
                        }

                        if (childNode.IsFull)
                        {
                            return false;
                        }

                        if (childNode.EndIndex < param.minValue)
                        {
                            return false;
                        }
                        return childNode.GetNotExistsNodes(param);
                    });
                    if (param.result.Count >= param.count)
                    {
                        return true;
                    }
                    if (AppendNotInRangeIds(param))
                    {
                        return true;
                    }
                }
                else if (node.Level == fileLevel)
                {
                    if (AppendNotInRangeIds(param))
                    {
                        return true;
                    }
                }
                else
                {
                    throw new NotSupportedException();
                }
                return false;
            }
        }

        internal IdTreeNode GetCloneNode(IdTreeNode current)
        {
            IdTreeNode cloneNode = new IdTreeNode
            {
                AddedRoot = null,
                IsFullChanged = false,
                BeginIndex = current.BeginIndex,
                EndIndex = current.EndIndex,
                Level = current.Level,
                IsFull = current.IsFull,
                ChildRoot = current.ChildRoot,
                Next = null
            };
            return cloneNode;
        }

        public IdTreeNode Clone()
        {
            lock (this)
            {
                IdTreeNode cloneRoot = GetCloneNode(this);
                Queue<IdTreeNode> queue = new Queue<IdTreeNode>();
                queue.Enqueue(null);
                queue.Enqueue(null);
                queue.Enqueue(cloneRoot);
                while (queue.Count > 0)
                {
                    IdTreeNode parentClone = queue.Dequeue();
                    IdTreeNode prevClone = queue.Dequeue();
                    IdTreeNode currentClone = queue.Dequeue();
                    if (parentClone != null)
                    {
                        if (prevClone == null)
                        {
                            parentClone.ChildRoot = currentClone;
                        }
                        else
                        {
                            prevClone.Next = currentClone;
                        }
                    }

                    IdTreeNode lastChildClone = null;
                    Each(currentClone.ChildRoot, (childNode) =>
                    {
                        var currentChildClone = GetCloneNode(childNode);
                        queue.Enqueue(currentClone);
                        queue.Enqueue(lastChildClone);
                        queue.Enqueue(currentChildClone);
                        lastChildClone = currentChildClone;
                        return false;
                    });
                }
                return cloneRoot;
            }
        }

        internal static bool Each(IdTreeNode header, Func<IdTreeNode, bool> action)
        {
            IdTreeNode node = header;
            while (node != null)
            {
                bool isFinish = action(node);
                if (isFinish)
                {
                    return true;
                }
                node = node.Next;
            }
            return false;
        }

        internal static bool Each(WrapedIdTreeNode header, Func<IdTreeNode, bool> action)
        {
            WrapedIdTreeNode node = header;
            while (node != null)
            {
                bool isFinish = action(node.Node);
                if (isFinish)
                {
                    return true;
                }
                node = node.Next;
            }
            return false;
        }



        internal void SaveAddedNodes(MergeSession ms, IdTreeNode changedParenNode, IVisitChangedNodes iVisitChangedNodes)
        {
            string basePath = ms.basePath;
            int[] calArray = ms.calArray;
            int dirMaxLevel = ms.calArray.Length - 1;
            if (changedParenNode.Level == dirMaxLevel + 1)
            {
                iVisitChangedNodes.SaveAddedFileItem(ms, changedParenNode);
            }
            else if (changedParenNode.Level > dirMaxLevel + 1)
            {
                throw new NotSupportedException();
            }
            else
            {
                Queue<IdTreeNode> nodeQueue = new Queue<IdTreeNode>();
                Each(changedParenNode.AddedRoot, (node) =>
                {
                    nodeQueue.Enqueue(node);
                    return false;
                });
                while (nodeQueue.Count > 0)
                {
                    IdTreeNode currentNode = nodeQueue.Dequeue();
                    if (currentNode.IsFull)
                    {
                        iVisitChangedNodes.RenameFullChangedItem(ms, currentNode);
                    }
                    else
                    {
                        if (currentNode.Level <= dirMaxLevel)
                        {
                            iVisitChangedNodes.CreateDirItem(ms, currentNode);

                            Each(currentNode.ChildRoot, (node) =>
                            {
                                nodeQueue.Enqueue(node);
                                return false;
                            });
                        }
                        else if (currentNode.Level == dirMaxLevel + 1)
                        {
                            iVisitChangedNodes.SaveFileAllItems(ms, currentNode);
                        }
                        else
                        {
                        }
                    }
                    MarkNodeUnChanged(currentNode);
                }
            }
        }

        internal void AppendAddedChildLink(IdTreeNode linkHeader)
        {
            Each(linkHeader, (node) =>
            {
                AppendAddedChildNode(node);
                return false;
            });
        }

        internal void AppendAddedChildNode(IdTreeNode childNode)
        {
            WrapedIdTreeNode addedTreeNode = new WrapedIdTreeNode
            {
                Node = childNode,
                Next = null
            };
            if (this.AddedRoot == null)
            {
                this.AddedRoot = addedTreeNode;
            }
            else
            {
                var oldRoot = this.AddedRoot;
                addedTreeNode.Next = oldRoot;
                this.AddedRoot = addedTreeNode;
            }
        }

        internal bool GetFullNodes(GetQueryNodesParam param)
        {
            int startI = Math.Max(this.BeginIndex, param.minValue);
            int endI = Math.Min(this.EndIndex, param.maxValue);
            for (int i1 = startI; i1 <= endI; i1++)
            {
                param.result.Add(i1);
                if (param.result.Count >= param.count)
                {
                    return true;
                }
            }
            return false;
        }

        public bool GetExistsNodes(GetQueryNodesParam param)
        {
            if (param.result.Count >= param.count)
            {
                return true;
            }

            if (this.BeginIndex > param.maxValue)
            {
                return false;
            }

            if (this.EndIndex < param.minValue)
            {
                return false;
            }

            lock (this)
            {
                if (this.IsFull)
                {
                    return GetFullNodes(param);
                }
                else
                {
                    Queue<IdTreeNode> queue = new Queue<IdTreeNode>();
                    queue.Enqueue(this);
                    while (queue.Count > 0)
                    {
                        IdTreeNode node = queue.Dequeue();
                        if (node.IsFull)
                        {
                            if (node.GetFullNodes(param))
                            {
                                return true;
                            }
                        }
                        else
                        {
                            Each(node.ChildRoot, (childNode) =>
                            {
                                if (param.result.Count >= param.count)
                                {
                                    return true;
                                }

                                if (childNode.BeginIndex > param.maxValue)
                                {
                                    return true;
                                }

                                if (childNode.EndIndex < param.minValue)
                                {
                                    return false;
                                }

                                queue.Enqueue(childNode);
                                return false;
                            });
                            if (param.result.Count >= param.count)
                            {
                                return true;
                            }
                        }
                    }
                }
                if (param.result.Count >= param.count)
                {
                    return true;
                }
                return false;
            }
        }
         
        public bool Except(GetQueryNodesParam param, IdTreeNode otherNode)
        {
            if (this.BeginIndex > param.maxValue)
            {
                return false;
            }

            if (this.EndIndex < param.minValue)
            {
                return false;
            }

            if (param.result.Count >= param.count)
            {
                return true;
            }

            lock (this)
            {
                if (this.IsFull)
                {
                    if (otherNode.IsFull)
                    {
                        return false;
                    }
                    else
                    {
                        return otherNode.GetNotExistsNodes(param);
                    }
                }
                else
                {
                    if (otherNode.IsFull)
                    {
                        return false;
                    }
                    else
                    {
                        if (this.ChildRoot == null || otherNode.ChildRoot == null)
                        {
                            if (this.ChildRoot != null || otherNode.ChildRoot != null)
                            {
                                throw new NotSupportedException();
                            }
                            return false;
                        }
                    }
                }
                IdTreeNode child1 = this.ChildRoot;
                IdTreeNode child2 = otherNode.ChildRoot;
                while (child1 != null && child2 != null)
                {
                    if (child1.BeginIndex == child2.BeginIndex)
                    {
                        if (child1.Except(param, child2))
                        {
                            return true;
                        }
                        child1 = child1.Next;
                        child2 = child2.Next;
                    }
                    else if (child1.BeginIndex < child2.BeginIndex)
                    {
                        if (child1.GetExistsNodes(param))
                        {
                            return true;
                        }
                        child1 = child1.Next;
                    }
                    else
                    {
                        child2 = child2.Next;
                    }
                }

                if (child1 != null)
                {
                    Each(child1, (node) =>
                    {
                        if (node.GetExistsNodes(param))
                        {
                            return true;
                        }
                        else
                        {
                            return false;
                        }
                    });
                    if (param.result.Count >= param.count)
                    {
                        return true;
                    }
                }
                return false;
            }
        }

        public bool MergeNode(IdTreeNode otherNode, MergeContext mergeContext)
        {
            if (otherNode == null)
            {
                return false;
            }
            lock (this)
            {
                if (this.IsFull)
                {
                    return false;
                }
                if (otherNode.IsFull)
                {
                    this.IsFull = true;
                    this.ChildRoot = null;
                    this.AddedRoot = null;
                    this.IsFullChanged = true;
                    mergeContext.SetChanged();
                    return true;
                }

                if (this.ChildRoot == null)
                {
                    if (otherNode.ChildRoot == null)
                    {
                        return false;
                    }
                    else
                    {
                        mergeContext.SetChanged();
                        this.ChildRoot = otherNode.ChildRoot;
                        AppendAddedChildLink(this.ChildRoot);
                        return otherNode.IsFull;
                    }
                }
                else
                {
                    if (otherNode.ChildRoot == null)
                    {
                        return false;
                    }
                    else
                    {
                        IdTreeNode child1 = this.ChildRoot;
                        IdTreeNode child2 = otherNode.ChildRoot;
                        IdTreeNode lastChild1 = null;
                        bool isChildrenFullChanged = false;
                        while (child1 != null && child2 != null)
                        {
                            if (child1.BeginIndex == child2.BeginIndex)
                            {
                                if (child1.MergeNode(child2, mergeContext))
                                {
                                    isChildrenFullChanged = true;
                                }
                                lastChild1 = child1;
                                child1 = child1.Next;
                                child2 = child2.Next;
                            }
                            else if (child1.BeginIndex < child2.BeginIndex)
                            {
                                lastChild1 = child1;
                                child1 = child1.Next;
                            }
                            else
                            {
                                if (child2.IsFull)
                                {
                                    isChildrenFullChanged = true;
                                }
                                var child2Next = child2.Next;
                                if (lastChild1 == null)
                                {
                                    this.ChildRoot = child2;
                                    child2.Next = child1;
                                }
                                else
                                {
                                    lastChild1.Next = child2;
                                    child2.Next = child1;
                                }
                                AppendAddedChildNode(child2);
                                child2 = child2Next;
                                mergeContext.SetChanged();
                            }
                        }

                        if (child1 != null)
                        { }
                        else if (child2 != null)
                        {
                            if (child2.IsFull)
                            {
                                isChildrenFullChanged = true;
                            }

                            if (lastChild1 == null)
                            {
                                this.ChildRoot = child2;
                            }
                            else
                            {
                                lastChild1.Next = child2;
                            }
                            AppendAddedChildLink(child2);
                            mergeContext.SetChanged();
                        }

                        if (isChildrenFullChanged)
                        {
                            IdTreeNode lastNode = null;
                            IdTreeNode childNode = this.ChildRoot;
                            int startIndex = this.BeginIndex;
                            while (childNode != null)
                            {
                                if (!childNode.IsFull)
                                {
                                    return false;
                                }
                                if (startIndex != childNode.BeginIndex)
                                {
                                    return false;
                                }
                                startIndex = childNode.EndIndex + 1;
                                childNode = childNode.Next;
                            }
                            if (startIndex == this.EndIndex + 1)
                            {
                                mergeContext.SetChanged();

                                this.IsFull = true;
                                this.ChildRoot = null;
                                this.AddedRoot = null;
                                this.IsFullChanged = true;
                                return true;
                            }
                            else
                            {
                                return false;
                            }
                        }
                        else
                        {
                            return false;
                        }
                    }
                }
            }
        }
    }
}